package datastructure.tree;

/**
 * Given a binary tree
struct Node {
Node leftChild;
Node rightChild;
Node nextRight;
}

Populate the nextRight pointers in each node.
You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)
 * 
 * @author Lei
 */
public class PopulateNextRightPointer {

    public static void populateNextRightPointer(TreeNode root) {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            root.left.nextRight = root.right;
        }

        if (root.right != null) {

            if (root.nextRight != null) {
                root.right.nextRight = root.nextRight.left;
            }
            else {
                root.right.nextRight = null;
            }
        }
        populateNextRightPointer(root.left);
        populateNextRightPointer(root.right);
    }
}
